#include "HashMap.h"



HashMap::HashMap(int Size):size(Size)
{
    this->array = new Node*[size];
    for(int i=0;i<size;i++)
    {
        array[i] = nullptr;//对数组里的指针初始化
    }
}




HashMap::~HashMap()
{
    for(int i=0;i<size;i++)
    {
        Node* travelPoint = array[i];

        while (travelPoint != nullptr) // 循环释放链表
        {
            Node* temp = travelPoint->next;
            delete travelPoint;
            travelPoint = temp;
        }
    }
    delete []array; //最后释放数组
}

void HashMap::Insert(const std::string &key, const ElementType &element)
{
    Node* node = new Node(key,element);
    
    //计算 哈希值  也就是想要的数组的下标
    int index = Hash(key);


    // if(array[index] == nullptr)
    // {
    //     array[index] = node;
    // }
    // else
    // {
        //头插法 链接链表
        node->next = array[index];  // 把原来有的节点 链接到新的节点后面
        array[index] = node; //然后把 新的节点 放进 当前下标位置
    // }
}

void HashMap::show()
{
    for(int i=0;i<size;i++)
    {
        Node* travelPoint = array[i];

        while (travelPoint != nullptr) // 循环释放链表
        {
            std::cout<<"hash值:"<<Hash(travelPoint->key)<<" "
                     <<"key:"<<travelPoint->key<<" "
                     <<"value:"<<travelPoint->value<<" "<<std::endl;
            travelPoint = travelPoint->next;
        }
    }
}

void HashMap::ShowByGroup()
{
  for(int i=0;i<size;i++)
    {
        Node* travelPoint = array[i];
        if(travelPoint == nullptr)
            continue;
        while (travelPoint != nullptr) // 循环释放链表
        {
            std::cout<<travelPoint->value<<" ";
                    
            travelPoint = travelPoint->next;
        } 
        std::cout<<std::endl;
    }  
}

ElementType *HashMap::Get(const std::string &key)
{
    Node* node = array[Hash(key)];  //O(1) ?
   
    while (node != nullptr) 
    {
        if(node->key == key)
        {
            return &node->value;
        }
        node = node->next;
    }
    return nullptr;
}

ElementType& HashMap::operator[](const std::string &key)
{
    ElementType* data = Get(key);
    //如果存在 返回
    if(data)
        return *data;

    // 如果不存在，新建
    else
    {
        Insert(key,"");
        return *Get(key);
    }
    
}

void HashMap::Remove(const std::string &key)
{
    Node * node = array[Hash(key)];
    if(node == nullptr)
        return;
    if(node->key == key)
    {
        array[Hash(key)] =  node->next;
        return;
    }
    while (node->next != nullptr)
    {
        if(node->next->key == key)
        {
            Node* freeNode = node->next;
            node->next = freeNode->next;
            delete freeNode;
            return;
        }
        node = node->next;
    }
    
}




int HashMap::Hash(const std::string &key)
{
    int hash = 0;
    //素数
    for(int i=0;i < key.size() ;i++)
    {
        // hash += key[i];
        
        
        
        hash = (hash * 31 + key[i]) % size;
    //使用上一个求出的和 乘一个素数增强 离散性 再加上这一次求出的ascii值，
    //之后再 取余Size 可以求出下一个哈希值
    }
    return hash;
}